package algorithm.bitmanipulation;

/**
 * leetcode : https://leetcode.com/problems/number-of-1-bits/description/
 * Difficulty: Easy
 *
 * hammingWeight
 * 给一个无符号数字，返回这个数字二进制中1的个数
 *
 * 例如:
 * input=11 (00000000000000000000000000001011)
 * output=3 (里面有3个1)
 *
 * @Author Antony
 * @Since 2018/7/4 15:35
 */
public class NumberOfOneBits {

    public static void main(String[] args) {
        int num_1 = 2147483647 + 1;
        System.out.println(num_1);
        System.out.println(Integer.toBinaryString(hammingWeight_2(num_1)));
    }

    // (beats 29.20%)
    public static int hammingWeight(int n) {
        int num = 0;
        for(int i=0; i<32; i++){
            num += (n>>>i)&1;
            // 或者可以: num += n&1; n >>>=1;
        }

        return num;
    }

    // (1ms - beats 98.42%)
    // 可以增加对0的判断，如果等于0了，那么剩下的就都是0，不需要移位了
    public static int hammingWeight_2(int n) {
        int num = 0;
        while(n != 0){
            num += n&1;
            n >>>=1;
        }
        return num;
    }
}
